#ifndef DMMATH_H
#define DMMATH_H

#include <random>
#include <stack>
#include <vector>
#include <set>
#include <functional>
#include <algorithm>

namespace KDM
{
	namespace math
	{
		template <typename Engine, typename DistributionType = int>
		class Random
		{
		public:
			typedef std::uniform_int<DistributionType> Distribution;
			typedef typename Distribution::result_type ResultType;

			Random(ResultType leftBorder, ResultType rightBorder) : 
			_generate(Engine(static_cast<ResultType>(time(NULL))), Distribution(leftBorder, rightBorder)){}

			ResultType operator()()
			{
				return _generate();
			}

		private:

			std::variate_generator<Engine, Distribution> _generate;
		};

		template<typename Index> inline Index getPowerOfTwo(const Index& digit)
		{
			Index result = 0;

			while (digit >> result)
			{
				result++;
			}

			return result - 1;
		}

		template<typename Index> inline Index setPowerOfTwo(Index power)
		{
			return (1 << power);
		}

		template<typename Index> class SortStack
		{
		public:
			SortStack(){}
			~SortStack()
			{
				while(!body.empty())
				{
					delete body.top();
					body.pop();
				}
			}
			void push(const Index& left, const Index& right)
			{
				if (right - left >= 1)
					body.push(new StackItem(left, right));
			}

			void pop(Index& left, Index& right)
			{
				left=body.top()->_left;
				right=body.top()->_right;

				delete body.top();
				body.pop();
			}
			bool isEmpty()
			{
				return body.empty();
			}

			Index getSize()
			{
				return (Index)body.size();
			}

		private:
			struct StackItem
			{
				Index _left;
				Index _right;
				StackItem(const Index& left, const Index& right) : _left(left), _right(right){}
			};

			std::stack<StackItem*> body;
		};

		template<typename DataType, typename Index> void sortSegment(std::vector<DataType>& resultVector, const Index leftBorder, Index rightBorder, std::function<bool (const DataType&, const DataType&)> isNeedChange)
		{
			if (rightBorder - leftBorder > 0)
			{
				std::vector<DataType>::iterator begin = resultVector.begin() + leftBorder, end = resultVector.begin() + rightBorder;

				std::sort(begin, end, isNeedChange);

				std::reverse(begin, end);
			}
		}

		template<typename DataType, typename Index> inline DataType getMedian(const std::vector<DataType>& resultVector, const Index& leftBorder, const Index& rightBorder)
		{
			Random<std::minstd_rand, Index> rnd(leftBorder, rightBorder);

			return resultVector[rnd()];
		}

		template<typename DataType, typename Index> void hoarSortStep(std::vector<DataType>& resultVector, Index leftBorder, Index rightBorder, std::function<bool (const DataType&, const DataType&)> isNeedChange, Index& terminator, DataType& medianResult)
		{
			rightBorder = rightBorder - 1;
			bool isWithinTheError = false;
			volatile const Index range = rightBorder - leftBorder + 1;
			volatile const Index maxDeviation = (Index)(range * 0.05f);
			volatile const Index halfRange = leftBorder + range / 2;
			DataType median;

			Index left, right;
			std::vector<DataType>::iterator leftIterator, rightIterator;
			DataType copy;

			while(isWithinTheError == false)
			{
				left = leftBorder;
				right = rightBorder;

				median = getMedian(resultVector, left, right);

				leftIterator = resultVector.begin() + left;
				rightIterator = resultVector.begin() + right;

				while(left < right)
				{
					while(isNeedChange(median, *(leftIterator)))
					{
						leftIterator++;
						left++;
					}

					while(isNeedChange(*(rightIterator), median))
					{
						rightIterator--;
						right--;
					}

					if (left < right)
					{
						copy = *(leftIterator);
						*(leftIterator) = *(rightIterator);
						*(rightIterator) = copy;

						leftIterator++;
						left++;

						rightIterator--;
						right--;
					}
					else
						if (left == right)
						{
							left++;
							right--;
						}
				}

				if (left < halfRange)
				{
					if ((halfRange - left) < maxDeviation)
					{
						isWithinTheError = true;
					}
					else
					{
						leftBorder = left;
					}
				}
				else
				{
					if ((left - halfRange) < maxDeviation)
					{
						isWithinTheError = true;
					}
					else
					{
						rightBorder = left;
					}
				}
			}
			while (!isNeedChange(resultVector[left], median))
			{
				left++;
			}
			terminator = left;

			medianResult = median;
		}

		template<typename DataType, typename Index> std::set<Index>  getThreadSegments(const std::vector<DataType>& resultVector, Index countThreads)
		{
			std::set<Index> segments;

			Index separaterIndex = 0;

			Index resultVectorSize = (Index)resultVector.size();

			if (countThreads > resultVectorSize)
			{
				countThreads = resultVectorSize;
			}

			for (Index i=0; i < (countThreads + 1); i++)
			{
				if (i == countThreads) 
					separaterIndex = resultVectorSize;
				else 
					separaterIndex = i * (resultVectorSize / countThreads);

				segments.insert(separaterIndex);
			}

			return std::move(segments);
		}

		template<typename DataType, typename Index> std::vector<Index> getSearchErasingSegments(const std::vector<Index>& filterBorders, std::set<Index> searchSegments)
		{
			std::vector<Index> searchErasingSegments = filterBorders;

			searchSegments.erase(0);

			for (std::set<Index>::iterator item = searchSegments.begin(); item != searchSegments.end(); item++)
			{
				searchErasingSegments.push_back(*item);
			}

			return std::move(searchErasingSegments);
		}

		template<typename DataType, typename Index> void eraseExcessElements(std::vector<DataType>& resultVector, const std::vector<Index>& searchErasingSegments)
		{
			std::vector<Index>::const_iterator item = searchErasingSegments.cbegin();

			Index left = 0, right = 0, range = 0;

			while (item != searchErasingSegments.cend())
			{
				range += right - left;
				left = *item++ - range;
				right = *item - range;

				if (left < right)
					resultVector.erase(resultVector.begin() + left, resultVector.begin() + right);

				item++;
			}
		}

    template<typename DataType, typename Index> void eraseExcessElements(std::vector<DataType>& resultVector, const std::vector<Index>& filterBorders, const std::set<Index>& searchSegments)
    {
      std::vector<Index> searchErasingSegments = KDM::math::getSearchErasingSegments<DataType, Index>(filterBorders, searchSegments);

      std::sort(searchErasingSegments.begin(), searchErasingSegments.end(), [](Index first, Index second){return first < second;});

      KDM::math::eraseExcessElements(resultVector, searchErasingSegments);
    }

		template<typename Index> Index getOrderBySegmentsCount(const Index& countThreads, const Index& threadsLimit)
		{
			Index segmentsCount;

			if (countThreads > threadsLimit)
			{
				segmentsCount = threadsLimit;
			}
			else
				segmentsCount = countThreads;

			segmentsCount = setPowerOfTwo(KDM::math::getPowerOfTwo(segmentsCount));

			return segmentsCount;
		}

    template<typename DataType, typename Index> void search(std::vector<DataType>& resultVector, const Index leftBorder, const Index rightBorder, std::function<bool (const DataType&)> isRequired, Index& eraseBorder)
    {
      Index j = leftBorder;
      for (Index i = leftBorder; i < rightBorder; i++)
      {
        if (isRequired(resultVector[i]))
        {
          resultVector[j] = resultVector[i];
          j++;
        }
      }
      eraseBorder = j;	
    }

    template<typename DataType, typename SelectType, typename Index> void select(const std::vector<DataType>& resultVector, std::vector<SelectType>& resultSelect, const Index leftBorder, const Index rightBorder, std::function<SelectType (const DataType&)> selectFunction)
	  {
		  for (Index i = leftBorder; i < rightBorder; i++)
		  {
			  resultSelect[i] = selectFunction(resultVector[i]);
		  }
	  }
	}
}

#endif